package com.code.leetcode._202508;

import com.code.leetcode._202503.ListNode;


//61 旋转链表
public class RotateRight {
    /**
     * 给你一个链表的头节点head，旋转链表，将链表每个节点向右移动k个位置
     * 示例1：输入：head = [1,2,3,4,5], k = 2
     * 输出：[4,5,1,2,3]
     * 示例2：输入：head = [0,1,2], k = 4
     * 输出：[2,0,1]
     **/
    public static void main(String[] args) {
        RotateRight r = new RotateRight();
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        System.out.println(r.rotateRight(head, 2));
    }

    /**
     * 闭合为环
     * 记给定链表的长度为n，注意到当向右移动的次数k>=n时，我们仅需要向右移动k mod n次即可。因为没n次移动都会让链表
     * 变为原状，这样我们可以知道，新链表的最后一个节点为原链表的第(n-1)-(k mod n)个节点(从0开始计数)
     * 这样，我们可以先将给定的链表连接成环，然后将指定位置断开
     * 具体代码中，我们首先计算处链表的长度n，并找到该链表的末尾节点，将其与头节点相连，这样就得到了闭合为环的链表。
     * 然后我们找到新链表的最后一个节点(即原链表的第(n-1)-(k mod n)个节点)，将当前闭合为环的链表断开，即可以得到我们
     * 所需要的结果
     * 特别的，当链表长度不大于1，或者k为n的倍数时，新链表将与原链表相同，我们无需进行任何处理。
     **/
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }// iter 来到了结尾
        int add = n - k % n;
        if (add == n) {
            return head;
        }
        iter.next = head;//将链表头接到末尾
        while (add-- > 0) {
            iter = iter.next;
        }//取到k-1位置的节点,将k-1节点的下一个节点置为null
        ListNode ret = iter.next;
        iter.next = null;//将
        return ret;
    }
}
